package com.cat.dataStructure03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/create-components-with-same-value/
 * @create 2025/11/17 09:06
 * @since JDK17
 */

public class Solution75 {
    List<Integer>[] g;
    int[] nums;
    int target;
    int dfs(int x, int fa) {
        int sum = nums[x], res;
        for (var y : g[x]) {
            if (y != fa) {
                res = dfs(y, x);
                if (res < 0) {
                    return -1;
                }
                sum += res;
            }
        }
        if (sum > target) {
            return -1;
        }
        return sum == target ? 0 : sum;
    }
    public int componentValue(int[] nums, int[][] edges) {
        int n = nums.length, max = 0, total = 0;
        g = new List[n];
        Arrays.setAll(g, x -> new ArrayList<>());
        for (var e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        this.nums = nums;
        for (var x : nums) {
            max = Math.max(x, max);
            total += x;
        }

        for (int i = total / max; i >= 0; i--) {
            if (total % i == 0) {
                target = total / i;
                if (dfs(0, -1) == 0) {
                    return i - 1;
                }
            }
        }

        return 0;
    }
}
